﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
//给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，
//该指针可以指向链表中的任何节点或空节点。
//构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，
//其中每个新节点的值都设为其对应的原节点的值。
//新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，
//并使原链表和复制链表中的这些指针能够表示相同的链表状态。
//复制链表中的指针都不应指向原链表中的节点 。
//例如，如果原链表中有 X 和 Y 两个节点，其中 X.random-- > Y 。
//那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random-- > y 。
//返回复制链表的头节点。
//用一个由 n 个节点组成的链表来表示输入 / 输出中的链表。
//每个节点用一个 [val, random_index] 表示：
//val：一个表示 Node.val 的整数。
//random_index：随机指针指向的节点索引（范围从 0 到 n - 1）；
//如果不指向任何节点，则为  null 。
//你的代码 只 接受原链表的头节点 head 作为传入参数。

  struct Node {
     int val;
     struct Node *next;
     struct Node *random;
  };
 

struct Node* copyRandomList(struct Node* head) {
    if (!head) return NULL;
    struct Node* p = head;
    struct Node* copyNode;
    while (p)
    {
        copyNode = (struct Node*)malloc(sizeof(struct Node));
        copyNode->val = p->val;
        copyNode->next = p->next;
        p->next = copyNode;
        p = copyNode->next;
    }

    p = head;
    while (p)
    {
        copyNode = p->next;
        copyNode->random = p->random ? p->random->next : NULL;
        p = p->next->next;
    }
    // 链接新结点(构建next指针)
    p = head->next;
    while (p->next)
    {
        p->next = p->next->next;
        p = p->next;
    }
    p->next = NULL;
    return head->next;
}

//给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
//
//有效字符串需满足：
//
//左括号必须用相同类型的右括号闭合。
//左括号必须以正确的顺序闭合。
//
//输入：s = "()"
//输出：true
//示例 2：

//输入：s = "()[]{}"
//输出：true

typedef char STDataType;
typedef struct Stack
{
    STDataType* a;
    int top;
    int capacity;
}ST;

void StackInit(ST* ps);

void StackDestory(ST* ps);

void StackPush(ST* ps, STDataType x);

void StackPop(ST* ps);

STDataType StackTop(ST* ps);

bool StackEmpty(ST* ps);

int StackSize(ST* ps);

void StackInit(ST* ps)           //初始化
{
    assert(ps);
    ps->a = NULL;
    ps->top = ps->capacity = 0;
}

void StackDestory(ST* ps)
{
    assert(ps);
    free(ps->a);
    ps->a = NULL;
    ps->top = ps->capacity = 0;
}

void StackPush(ST* ps, STDataType x)        //入栈
{
    assert(ps);
    if (ps->top == ps->capacity)
    {
        int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
        STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
        if (tmp == NULL)
        {
            perror("realloc fail");
            exit(-1);
        }
        ps->a = tmp;
        ps->capacity = newcapacity;
    }
    ps->a[ps->top] = x;
    ps->top++;
}

void StackPop(ST* ps)            //出栈
{
    assert(ps);
    assert(!StackEmpty(ps));
    --ps->top;
}

STDataType StackTop(ST* ps)            //获取栈顶元素
{
    assert(ps);
    assert(!StackEmpty(ps));
    return ps->a[ps->top - 1];
}

bool StackEmpty(ST* ps)         //检测栈是否为空，如果为空返回非零结果，如果不为空返回0
{
    assert(ps);
    return ps->top == 0;
}

int StackSize(ST* ps)          //
{
    assert(ps);
    return ps->top;
}
bool isValid(char* s) {
    ST st;
    StackInit(&st);
    while (*s)
    {
        if (*s == '{' || *s == '[' || *s == '(')
        {
            StackPush(&st, *s);
        }
        else {
            if (StackEmpty(&st))
                return false;
            char top = StackTop(&st);
            StackPop(&st);
            if ((*s == '}' && top != '{') ||
                (*s == ']' && top != '[') ||
                (*s == ')' && top != '('))
            {
                return false;
            }
        }
        ++s;

    }
    //栈不为空，说明数量不匹配
    bool flag = StackEmpty(&st);
    StackDestory(&st);
    return flag;
}